package 每日一题;

import java.util.HashMap;

/**
 * 1094. 拼车
 * 提示
 * 中等
 * 340
 * 相关企业
 * 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
 *
 * 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
 *
 * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
 *
 *
 *
 * 示例 1：
 *
 * 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
 * 输出：false
 * 示例 2：
 *
 * 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
 * 输出：true
 *
 *
 * 提示：
 *
 * 1 <= trips.length <= 1000
 * trips[i].length == 3
 * 1 <= numPassengersi <= 100
 * 0 <= fromi < toi <= 1000
 * 1 <= capacity <= 105
 */
public class T1094_拼车 {

    //统计每一站 下车 和上车的人数 遍历所有站点 只要不超载 就可以接送所有的乘客

    //使用差分数组 遍历一次数组 当某一个点 数值大于capacity 即为false
    public static boolean carPooling(int[][] trips, int capacity) {

        int count_car_people = 0;

        //统计每一站 上下车人数

        //上车人数
        HashMap<Integer, Integer> car_up_map = new HashMap<>();
        //下车人数
        HashMap<Integer, Integer> car_down_map = new HashMap<>();


        for (int[] trip : trips) {
            Integer car_up_Num = car_up_map.getOrDefault(trip[1], 0);
            Integer car_down_num = car_down_map.getOrDefault(trip[2], 0);
            car_up_map.put(trip[1], car_up_Num + trip[0]);
            car_down_map.put(trip[2], car_down_num + trip[0]);
        }

        //最大数1000个站点
        for (int i = 0; i <= 1000; i++) {

            //没有人上车了
            if (car_up_map.size() == 0) {
                break;
            }

            //判断 当前车站是否有人下车
            Integer down_num = car_down_map.getOrDefault(i, 0);
            car_down_map.remove(i);
            //判断是否有人上车
            Integer up_num = car_up_map.getOrDefault(i, 0);
            car_up_map.remove(i);
            count_car_people = count_car_people + up_num - down_num;

            if (count_car_people > capacity) {
                return false;
            }


        }

        return true;


    }

    public static void main(String[] args) {
        carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 4);
    }

}
